package dp;

import java.util.Arrays;

/**
 * 746. 使用最小花费爬楼梯
 * 创建时间：2024/6/25 上午11:54
 */
public class 使用最小花费爬楼梯_746 {
    /**
     * 定义d(i) 表示从 0或1 爬到i 所花的最小费用
     * 因为可以分1步和2步走，枚举最后一步：
     * 最后一步为 1 个台阶时：
     * d(i) = d(i-1) + cost[i-1]
     * 最后一步为 2 个台阶时：
     * d(i) = d(i-2) + cost[i-2]
     *
     * 因为求花费最小：
     * d(i) = min(d(i-1) + cost[i-1], d(i-2) + cost[i-2])
     *
     * 递归边界：dfs(0)=0,dfs(1)=0。爬到 0 或 1 无需花费，因为一开始在 0 或 1。
     */
    int[] cost;
    int[] memo;
    // 递归 + 记忆化搜索
    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        memo = new int[cost.length + 1];
        Arrays.fill(memo, -1);
        return dfs(cost.length);
    }

    public int dfs(int n) {
        if (n < 2) {
            return 0;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        return memo[n] = Math.min(dfs(n - 1) + cost[n - 1], dfs(n - 2) + cost[n - 2]);
    }

    // 递推
    public int minCostClimbingStairs2(int[] cost) {
        int f0 = 0, f1 = 0;
        int ans = 0;
        for (int i = 1; i < cost.length; i++) {
            ans = Math.min( f0 + cost[i - 1], f1 + cost[i]);
            f0 = f1;
            f1 = ans;
        }
        return ans;
    }
}
